Electronic design systems go through a series of transformations in terms of levels of abstractions from their design to their getting manufactured. Examples of the electronic design systems may include but are not limited to Integrated Circuit (ICs), IC Packages, Micro Electronic Mechanical Systems (MEMS), Printed Circuit Boards (PCBs), Multi-Chip Modules (MCMs), Photo Mask data, Laser Direct Imaging (LDI), E-Beam technology, silicon debugging, and failure analysis. Each transformation adds more details to the description of the previous level of abstraction of the electronic design system. As a result of this at each succeeding level of abstraction the data becomes voluminous and more specific as compared to a preceding level of abstraction. The lowest level of abstraction, i.e., geometrical layout of an electronic design system, uses geometrical figures like polygons, lines and vertices, which are used to represent locations and orientations of sub-components of the electronic design system with respect to each others. The data generated using the geometrical layout can be called geometrical layout design data. Large memory is required for storing, processing, analyzing, and modifying geometrical layout design data leading to the manufacturing process for the electronic design systems.
The geometrical layout design data is represented using a plurality of polygons. Each polygon corresponds to the whole or a part of an equipotential area in an electronic design system. The information in a polygon has topological information, dimensional information and spatial information. The topological information is the property of a polygon corresponding to the relational information between the vertices of the polygon, which is also sometimes loosely called as shape or pattern of the polygon. The dimensional information gives the polygon a definite size and area. Further, the spatial information gives the exact location to the polygon such that it can be placed spatially in X, Y or Z (layer) coordinates.
In conventional systems, topological information is extracted by capturing lengths of the edges of each polygon in a sequence along with the angle between the edges. Another conventional system, extracts dimensional information and spatial information of a polygon by identifying the cartesian coordinates of the vertices of the polygon in absolute or relative form. Thereafter, the dimensional information of the polygon is extracted from the coordinates of adjacent vertices. The spatial information is extracted based on the coordinate information. In another conventional system, a polygon in the geometrical layout design data is instantiated. Based on the instantiated polygon, topological and dimension information is extracted.
However, the conventional systems that store the geometrical layout design data do not keep the topological information about the polygons explicitly or in easily retrievable form. As a result, topological information of a polygon has to be explicitly extracted from the stored geometrical layout design data through computationally intensive steps, as a result of which operations based on topology of a polygon are more computationally expensive in terms of memory and time. Further, while analyzing geometrical layout design data for topological information or operations which operate on topologies, each polygon has to be analyzed separately that demands additional resources in terms storage in Random Access Memory (RAM). The geometrical layout design data is very often large as compared to the size of the RAM making it difficult to store large amount of polygonal data only in the RAM.
Some conventional methods provide virtual memory systems, which convert a portion of the hard disk into virtual RAM, usually called virtual memory, to store the polygonal data and only parts of polygon data that are required for computations are moved into the RAM. However the data fetching from the virtual memory on a hard disk is slower as compared to the data fetching from the RAM, thus a huge time penalty is incurred whenever polygonal data has to be fetched from the virtual memory on a hard disk.
A number of operations carried out on geometrical layout design data are topology-centric. Hence, these topology-centric operations can potentially be carried out on one polygon and re-used for all polygons with similar topologies. This could potentially speed up the operations significantly. However, as the conventional methods do not store the topological characteristics of polygons explicitly or in easily retrievable form, the conventional methods can not make use of the above scheme for speeding up the topology-centric operations on geometrical layout design data.
There is therefore a need for methods and systems for extracting information regarding the topology of a polygon, retaining this information in a database and utilizing the topological information efficiently for further processing of the geometrical layout design data.